package arithmetic2.day04;

/*
    将链表逆置
 */
public class Demo04 {
    public static void main(String[] args) {
        MyList myList = new MyList();
        myList.tailAdd(1);
        myList.tailAdd(2);
        myList.tailAdd(3);
        myList.print();
        myList.reverse();
        myList.print();
    }
}

class MyList {
    private N head;
    int size;

    //尾插法
    public void tailAdd(int value) {
        if (head == null) {
            head = new N(value, null);
            size++;
            return;
        }
        N temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new N(value, null);
        size++;
    }

    //头插法
    private void headAdd(int value) {
        if (head == null) {
            head = new N(value, null);
            return;
        }
        if (head.next == null) {
            N temp = head;
            head = new N(value, null);
            head.next = temp;
            return;
        }
        N temp = head;
        head = new N(value, null);
        head.next = temp;
    }

    //将链表逆置
    public void reverse() {
        if (head != null && head.next != null) {
            N newHead = null;
            //将所有元素使用头插法插进新链表
            N temp = head;
            while (temp != null) {
                if (newHead == null) {  //没有元素
                    newHead = new N(temp.value, null);
                } else {    //有元素
                    N n = newHead;
                    newHead = new N(temp.value, null);
                    newHead.next = n;
                }
                temp = temp.next;
            }
            //将头结点换为新的头节点
            head = newHead;
        }
    }

    //清空链表
    public void clear() {
        head = null;
        size = 0;
    }

    //将链表中的值放在数组中返回
    public int[] toArray() {
        int arr[] = new int[size];
        int index = 0;
        if (head != null) {
            N temp = head;
            while (temp != null) {
                arr[index] = temp.value;
                index++;
                temp = temp.next;
            }
        }
        return arr;
    }

    //将链表根据key划分为三部分
    public void partition(int key) {
        if (head != null) {
            //定义6个变量,小于部分的头、小于部分的尾、等于部分的头、等于部分的尾、大于部分的头、大于部分的尾
            N sh, st, eh, et, bh, bt;
            sh = st = eh = et = bh = bt = null;
            //遍历链表
            N temp = head;
            while (temp != null) {
                if (temp.value < key) {
                    if (sh == null) {
                        sh = temp;
                    }
                    if (st != null) {
                        st.next = temp;
                    }
                    st = temp;
                }
                if (temp.value == key) {
                    if (eh == null) {
                        eh = temp;
                    }
                    if (et != null) {
                        et.next = temp;
                    }
                    et = temp;
                }
                if (temp.value > key) {
                    if (bh == null) {
                        bh = temp;
                    }
                    if (bt != null) {
                        bt.next = temp;
                    }
                    bt = temp;
                }
                temp = temp.next;
            }
            //将三段串起来
            st.next = eh;
            et.next = bh;
            bt.next = null;
            //将原来的头结点替换成新的头节点
            head = sh;
        }
    }

    //遍历链表
    public void print() {
        if (head != null) {
            N temp = head;
            while (temp != null) {
                System.out.print(temp.value + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    }
}

class N {
    int value;
    N next;

    public N() {
    }

    public N(int value, N next) {
        this.value = value;
        this.next = next;
    }
}
